package fun.ticsmyc.question;

import org.junit.Test;

import java.util.*;

/**
 * @author Ticsmyc
 * @date 2020-09-18 10:05
 */
public class 有重复数字的数组全排列 {

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums ==null || nums.length<1){
            return res;
        }
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dfs(nums,used,0,new LinkedList<>());
        return res;
    }

    private void dfs(int[]nums, boolean[] used, int pos,Deque<Integer> path){
        if(pos == nums.length){
            res .add (new ArrayList<>(path));
            return;
        }

        for(int i=0;i<nums.length;++i){
            if(used[i]) continue;
            if(i!=0 && nums[i]==nums[i-1] && !used[i-1]){
                continue;
            }

            used[i] = true;
            path.offerLast(nums[i]);
            dfs(nums,used,pos+1,path);
            path.pollLast();
            used[i]=false;
        }
    }




    @Test
    public void test(){
        int[] arr= new int[] {1,1,2,2};
        System.out.println(permuteUnique(arr));
    }
}
